﻿
Imports osi.root.connector

Partial Public Class bt(Of T)
    Public Class iterator
        Implements IComparable(Of iterator)

        Public Shared ReadOnly [end] As iterator

        Shared Sub New()
            [end] = New iterator(Nothing, True)
        End Sub

        Private ReadOnly n As node

        Private Sub New(ByVal n As node, ByVal internal As Boolean)
            Me.n = n
        End Sub

        Friend Sub New(ByVal n As node)
            k_assert(Not n Is Nothing)
            Me.n = n
        End Sub

        Friend Function node() As node
            Return n
        End Function

        Private Function move_next(ByVal that As UInt32) As iterator
            k_assert(that > 0)
            Dim n As node = Nothing
            n = Me.n
            For i As UInt32 = 0 To CUInt(that - 1)
                k_assert(Not n Is Nothing)
                If n.has_right_child() Then
                    n = n.right_child().min()
                ElseIf n.is_left_subtree() Then
                    n = n.parent()
                Else
                    While n.is_right_subtree()
                        n = n.parent()
                    End While
                    If n.is_root() Then
                        Return [end]
                    Else
                        k_assert(n.is_left_subtree())
                        n = n.parent()
                    End If
                End If
            Next
            k_assert(Not n Is Nothing)
            Return New iterator(n)
        End Function

        Private Function move_prev(ByVal that As UInt32) As iterator
            k_assert(that > 0)
            Dim n As node = Nothing
            n = Me.n
            For i As UInt32 = 0 To CUInt(that - 1)
                k_assert(Not n Is Nothing)
                If n.has_left_child() Then
                    n = n.left_child().max()
                ElseIf n.is_right_subtree() Then
                    n = n.parent()
                Else
                    While n.is_left_subtree()
                        n = n.parent()
                    End While
                    If n.is_root() Then
                        Return [end]
                    Else
                        k_assert(n.is_right_subtree())
                        n = n.parent()
                    End If
                End If
            Next
            k_assert(Not n Is Nothing)
            Return New iterator(n)
        End Function

        '1. iterator / reverse_iterator are combined together
        '2. do not allow to - from end, it's not must-have
        Public Shared Operator +(ByVal this As iterator, ByVal that As Int32) As iterator
            If that = 0 OrElse this Is Nothing OrElse this.n Is Nothing Then
                Return this
            ElseIf that > 0 Then
                Return this.move_next(CUInt(that))
            Else
                k_assert(that < 0)
                Return this.move_prev(CUInt(-that))
            End If
        End Operator

        Public Shared Operator -(ByVal this As iterator, ByVal that As Int32) As iterator
            If that = 0 OrElse this Is Nothing OrElse this.n Is Nothing Then
                Return this
            ElseIf that > 0 Then
                Return this.move_prev(CUInt(that))
            Else
                k_assert(that < 0)
                Return this.move_next(CUInt(-that))
            End If
        End Operator

        Public Function is_end() As Boolean
            Return n Is Nothing AndAlso
                   (Not isdebugmode() OrElse
                    k_assert(object_compare(Me, [end]) = 0))
        End Function

        Public Function is_not_end() As Boolean
            Return Not is_end()
        End Function

        Public Function value() As T
            Return n.value()
        End Function

        Public Shared Operator +(ByVal this As iterator) As T
            Return If(this = [end], Nothing, this.n.value())
        End Operator

        Public Shared Operator =(ByVal this As iterator, ByVal that As iterator) As Boolean
            Dim c As Int32 = 0
            c = object_compare(this, that)
            If c = object_compare_undetermined Then
                k_assert(Not this Is Nothing)
                k_assert(Not that Is Nothing)
                Return (object_compare(this.n, that.n) = 0)
            Else
                Return (c = 0) OrElse
                       (this Is Nothing AndAlso that.is_end()) OrElse
                       (that Is Nothing AndAlso this.is_end())
            End If
        End Operator

        Public Shared Operator <>(ByVal this As iterator, ByVal that As iterator) As Boolean
            Return Not (this = that)
        End Operator

        Public Function CompareTo(ByVal other As bt(Of T).iterator) As Int32 _
                                 Implements IComparable(Of bt(Of T).iterator).CompareTo
            Return If(Me = other, 0, -1)
        End Function
    End Class
End Class
